class Solution {
    private int[] disjointSet;
    private int[] dx = new int[] {0, 1, 0, -1};
    private int[] dy = new int[] {1, 0, -1, 0};
    public int numIslands(char[][] grid) {
        int count = grid.length * grid[0].length;
        disjointSet = new int[count];
        for (int i = 0; i < count; i++) {
            disjointSet[i] = i;
        }
        for (int i = 0; i < grid.length; i++) {
            for  (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '0') continue;
                int idx = grid[0].length * i + j;
                for (int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if (nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length || grid[nx][ny] == '0') continue;
                    unionSet(idx, nx * grid[0].length + ny);
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '0') continue;
                int idx = grid[0].length * i + j;
                if (disjointSet[idx] == idx) ans++;
            }
        }
        return ans;
    }
    private int find(int x) {
        if (disjointSet[x] == x) return x;
        return disjointSet[x] = find(disjointSet[x]);
    }
    private void unionSet(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) {
            disjointSet[y] = x;
        }
    }
}
/**
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1
 */
